package com.lw.leetcode.bingChaJi.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 924. 尽量减少恶意软件的传播
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/12 17:46
 */
public class MinMalwareSpread924 {

    private int[] arr;

    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        int length = graph.length;
        arr = new int[length];
        int[] counts = new int[length];
        int[] flags = new int[length];
        int max = 0;
        int index = -1;
        for (int i = 0; i < length; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (graph[i][j] == 1) {
                    int a = find(i);
                    int b = find(j);
                    if (a != b) {
                        arr[Math.max(a, b)] = Math.min(a, b);
                    }
                }
            }
        }
        for (int i = 0; i < length; i++) {
            counts[find(i)]++;
        }
        for (int v : initial) {
            flags[find(v)]++;
        }
        for (int t : initial) {
            int v = find(t);
            if (flags[v] == 1 && counts[v] > max) {
                max = counts[v];
                index = t;
            }
        }
        if (index == -1) {
            return initial[0];
        }
        return index;
    }

    private int find(int v) {
        if (arr[v] == v) {
            return v;
        }
        int t = find(arr[v]);
        arr[v] = t;
        return t;
    }

}
